/*  
 * i-OSGi - Tunable Bundle Isolation for OSGi
 * Copyright (C) 2011  Sven Schulz
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.iosgi.benchmark;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Random;

import org.jgrapht.Graph;
import org.jgrapht.VertexFactory;
import org.jgrapht.generate.GraphGenerator;

/**
 * @author Sven Schulz
 */
public class RandomGraphGenerator<V, E> implements GraphGenerator<V, E, V> {

	private final int numberOfVertices;
	private final int numberOfEdges;
	private final boolean selfLoops;
	private final Random random;

	public RandomGraphGenerator(int numberOfVertices, int numberOfEdges,
			boolean selfLoops, Random random) {
		this.numberOfVertices = numberOfVertices;
		this.numberOfEdges = numberOfEdges;
		this.selfLoops = selfLoops;
		this.random = random;
	}

	@Override
	public void generateGraph(Graph<V, E> graph, VertexFactory<V> factory,
			Map<String, V> resultMap) {

		/* Add vertices. */
		List<V> vertices = new ArrayList<V>(numberOfVertices);
		for (int i = 0; i < numberOfVertices; i++) {
			V v = factory.createVertex();
			vertices.add(v);
			graph.addVertex(v);
		}

		/* Add edges. */
		double prob = numberOfEdges
				/ (double) MIPSolving.arithmeticSeriesSum(numberOfVertices - 1,
						1, 1);
		for (int i = 0; i < numberOfVertices; i++) {
			for (int j = 0; j < numberOfVertices; j++) {
				if (!selfLoops && i == j)
					continue;
				if (random.nextDouble() < prob) {
					graph.addEdge(vertices.get(i), vertices.get(j));
				}
			}
		}

		/* Add edges. */
		while (graph.edgeSet().size() < numberOfEdges) {
			V u = vertices.get(random.nextInt(vertices.size()));
			V v = vertices.get(random.nextInt(vertices.size()));
			if (!selfLoops && u.equals(v)) {
				continue;
			}
			graph.addEdge(u, v);
		}

		/* Remove edges. */
		List<E> edges = new ArrayList<E>(graph.edgeSet());
		while (graph.edgeSet().size() > numberOfEdges) {
			E e = edges.remove(random.nextInt(edges.size()));
			graph.removeEdge(e);
		}
	}

}
